BZOJ4872【SHOI2017】分手是祝愿 <概率DP>

Problem

【SHOI2017】分手是祝愿

Description

Zeit und Raum trennen dich und mich.
时空将你我分开。在玩一个游戏，这个游戏由个灯和个开关组成，给定这个灯的初始状态，下标为从到的正整数。每个灯有两个状态亮和灭，我们用来表示这个灯是亮的，用表示这个灯是灭的，游戏的目标是使所有灯都灭掉。但是当操作第个开关时，所有编号为的约数（包括和）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。这个策略需要的操作次数很多，想到这样的一个优化。如果当前局面，可以通过操作小于等于个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于步）操作这些开关。想知道按照这个策略（也就是先随机操作，最后小于等于步，使用操作次数最小的操作方法）的操作次数的期望。这个期望可能很大，但是发现这个期望乘以一定是整数，所以他只需要知道这个整数对取模之后的结果。

Input

第一行两个整数 , 。
接下来一行个整数，每个整数是或者，其中第个整数表示第个灯的初始情况。
,

Output

一行，为操作次数的期望乘以对取模之后的结果。

Sample Input

1 2	4 0 0 0 1 1

Sample Output

Source

黑吉辽沪冀晋六省联考

标签：概率DP

Solution

显然一种可行的最优解方案是从大往小操作，如果当前灯是亮的，则将其及其约数编号的灯状态翻转。
预处理初始状态通过这种状态操作到全部灭掉的次数，记为。
令为还剩步全部灭掉时的期望步数，有

发现的转移带环。将进行差分，记为，即。那么有

由此可在时间内算出，累加可知。

Code

#include <bits/stdc++.h>
#define P 100003
#define MAX_N 100000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, cnt; lnt ans;
lnt fac[MAX_N+5], inv[MAX_N+5];
bool a[MAX_N+5]; lnt g[MAX_N+5];
void init() {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= n; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
}
int main() {
    read(n), read(m), init();
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = n; i; cnt += a[i--])
        for (int j = (i<<1); j <= n; j += i) a[i] ^= a[j];
    g[n] = 1; for (int i = 1; i <= m; i++) g[i] = 1;
    for (int i = n-1; i > m; i--)
        g[i] = (1LL*(n-i)*inv[i]%P*g[i+1]%P+1LL*n*inv[i]%P)%P;
    for (int i = 1; i <= cnt; i++) ans = (ans+g[i])%P;
    return printf("%lld\n", ans*fac[n]%P), 0;
}